<?php
class LocalAlignator
{
    public $test, $tested;
    const GAP = -6;
    const MATCH = 5;
    const PENALTY = -3;
    /**
     * @var alligment
     */
    protected $max;
    protected $map;

    public $compareMatrix;

    function __construct($test, $tested)
    {
        $this->run($test, $tested);
    }

    public function resetVar()
    {
        $this->test = null;
        $this->tested = null;
        $this->max = null;
        $this->map = null;
        $this->compareMatrix = null;
    }

    function run($test, $tested)
    {
        $this->resetVar();
        $this->test = $test;
        $this->tested = $tested;
        $this->buildMap();
    }

    function buildMap()
    {
        if (empty($this->compareMatrix)) $this->initMatrix();
        $nulls = array_fill(0, strlen($this->test) + 1, 0);
        $this->map = array_fill(0, strlen($this->tested) + 1, $nulls);

        for ($i = 1; $i < sizeof($this->map); $i++) {
            for ($j = 1; $j < sizeof($this->map[0]); $j++) {
                $a = $this->hNum($i, $j);
                $this->setMax($i, $j, $a);
                $this->map[$i][$j] = $a;
            }
        }
    }

    function setMax($y, $x, $sum)
    {
        if ($this->max == null) {
            $this->max = new alligment();
            $this->max->x = $x;
            $this->max->y = $y;
            $this->max->sum = $sum;
        }
        elseif ($this->max->sum <= $sum) {
            $this->max->x = $x;
            $this->max->y = $y;
            $this->max->sum = $sum;
        }
    }

    function printMatrix()
    {
        echo "<table style='border: solid 1px;'><tr><td></td><th>-</th>";
        $str = str_split($this->test);
        foreach ($str as $s) {
            echo "<th>$s</th>";
        }
        echo "</tr>";
        foreach ($this->map as $s => $c) {
            $head = $s == 0 ? "-" : $this->tested{$s - 1};
            echo "<tr style='border: solid 1px;'><th>" . $head . "</th>";
            foreach ($c as $x) {
                echo "<td style='border: solid 1px;'>" . $x . "</td>";
            }
            echo "</tr>";
        }
        echo "</table>";


    }

    function allign()
    {
        $hitStr = "";
        $testedStr = "";
        $testStr = "";
        if (strlen($this->test) - ($this->max->x) > 0) {
            $hitStr = implode("", array_fill(0, strlen($this->test) - ($this->max->x), " "));
            $testedStr = implode("", array_fill(0, strlen($this->test) - ($this->max->x), "-"));
            $testStr = substr($this->test, $this->max->x);
        }
        $x = $this->max->x;
        $y = $this->max->y;
        $current = $this->max->sum;
        $t2 = substr($this->tested, $y, strlen($this->tested) - 1);
        while ($current > 0) {
            $testedChar = $this->tested{$y - 1};
            $testChar = $this->test{$x - 1};


            $up = $this->map[$y - 1][$x];
            $left = $this->map[$y][$x - 1];
            if ($current < max($up, $left)) {
                if ($up < $left) {
                    $testedChar = "-";
                    $x--;
                }
                else {
                    $testChar = "-";
                    $y--;
                }
            }
            else {
                $x--;
                $y--;
            }

            if ($testChar == $testedChar) {
                $hitStr = "|" . $hitStr;
            }
            else {
                $hitStr = " " . $hitStr;
            }
            $testedStr = $testedChar . $testedStr;
            $testStr = $testChar . $testStr;
            $current = $this->map[$y][$x];
        }
        if ($x > 0) {
            $testStr = substr($this->test, 0, $x) . $testStr;
            $hitStr = implode("", array_fill(0, $x, " ")) . $hitStr;
            $testedStr = implode("", array_fill(0, $x, "-")) . $testedStr;
        }

        $t1 = substr($this->tested, 0, $y);
        if (strlen($t2) != 0) {
            $testedStr = $testedStr . $t2;
            $testStr = $testStr . implode("", array_fill(0, strlen($t2), "-"));
        }
        if (strlen($t1) != 0) {
            $testedStr = $t1 . $testedStr;
            $testStr = implode("", array_fill(0, strlen($t1), "-")) . $testStr;
            $hitStr = implode("", array_fill(0, strlen($t1), " ")) . $hitStr;
        }

        return array(
            "string1" => $testedStr,
            "string2" => $testStr,
            "compare" => $hitStr
        );
    }

    function showMax()
    {
        var_dump($this->max);
    }

    function getMax()
    {
        return $this->max;
    }

    function hNum($i, $j)
    {
        $diag = $this->map[$i - 1][$j - 1] + $this->compareMatrix[$this->tested{$i - 1}][$this->test{$j - 1}];
        $down = $this->map[$i - 1][$j] + self::GAP;
        $right = $this->map[$i][$j - 1] + self::GAP;
        $max = max($diag, $down, $right, 0);
        return $max;
    }


    function initMatrix()
    {
        $this->compareMatrix =
            array("A" => array("A" => self::MATCH, "C" => self::PENALTY, "G" => self::PENALTY, "T" => self::PENALTY),
                  "C" => array("A" => self::PENALTY, "C" => self::MATCH, "G" => self::PENALTY, "T" => self::PENALTY),
                  "G" => array("A" => self::PENALTY, "C" => self::PENALTY, "G" => self::MATCH, "T" => self::PENALTY),
                  "T" => array("A" => self::PENALTY, "C" => self::PENALTY, "G" => self::PENALTY, "T" => self::MATCH));
    }

    function getPathScore()
    {
        return $this->getMax()->sum;
    }

    function getComparedStrings()
    {
        return $this->allign();
    }

}

class alligment
{
    public $x, $y, $sum = 0;
}
